1. Field of the Invention
The present invention relates generally to a communication system, and in particular, to an apparatus and method for encoding/decoding Block Low Density Parity Check (LDPC) codes having a variable coding rate.
2. Description of the Related Art
With the rapid development of communication systems, there is a need for the development of a technology capable of transmitting high-capacity data approaching the capacity of wire networks even in wireless networks. Due to the demand for a high-speed, high-capacity communication system capable of processing and transmitting various information, such as video, multimedia and wireless data, as well as voice service data, increasing system transmission efficiency using an appropriate channel coding scheme serves as an essential factor for improvement of system performance. However, communication systems, due to their characteristics, may inevitably suffer from errors caused by noise, interference, fading, etc., according to channel conditions during data transmission. Therefore, communication systems suffer a loss of information data due to error.
In order to reduce information data loss caused by error, communication systems use various error control schemes according to channel characteristics, thereby contributing to improvement of system reliability. Of error control schemes, an error correction code-based error control scheme is widely used.
Typical error correction codes include turbo codes and Low Density Parity Check (LDPC) codes.
It is well known that turbo codes are superior in performance gain to a convolutional code conventionally used for error correction, during high-speed data transmission. Turbo codes are advantageous because they can efficiently correct errors caused by noise generated in a transmission channel, thereby increasing reliability of data transmission.
In addition, an LDPC code can be decoded using an iterative decoding process based on a sum-product process in a factor graph. Because a decoder for an LDPC code uses a sum-product process-based iterative decoding process, it is lower in complexity than a decoder for turbo codes. In addition, a decoder for an LDPC code is easy to implement with a parallel processing decoder, compared with a decoder for turbo codes.
Meanwhile, Shannon's channel coding theorem shows that reliable communication is possible only at a data rate not exceeding a channel capacity. However, Shannon's channel coding theorem has proposed no detailed channel coding/decoding methods for supporting a data rate up to the channel capacity limit. Although a random code having a very large block size shows performance approximating the channel capacity limit of Shannon's channel coding theorem, it is actually impossible to implement a Maximum A Posteriori (MAP) or Maximum Likelihood (ML) decoding method because of its heavy calculation load.
Turbo codes were proposed by Berrou, Glavieux and Thitimajshima in 1993, and have superior performance approximating the channel capacity limit of Shannon's channel coding theorem. The proposal of turbo codes triggered off an active research on iterative decoding and graphical expression of codes, and LDPC codes proposed by Gallager in 1962 are newly spotlighted in the research. Cycles exist in a factor graph of turbo codes and LDPC codes, and it is well known that iterative decoding in the factor graph of LDPC codes where cycles exist is suboptimal. Also, it has been experimentally proved that LDPC codes have excellent performance through iterative decoding. An LDPC code ever known to have the highest performance shows performance having a difference of only about 0.04 decibels (dB) at the channel capacity limit of Shannon's channel coding theorem at a bit error rate (BER) 10−5, using a block size 107. In addition, although an LDPC code defined in Galois field (GF) with q>2, i.e. GF(q), increases in complexity in its decoding process, it is much superior in performance to a binary code. However, there has been provided no satisfactory theoretical description of successful decoding by an iterative decoding process for an LDPC code defined in GF(q).
LDPC codes, proposed by Gallager, are defined by a parity check matrix in which major elements have a value of 0 and minor elements, except elements having a value of 0, have a non-zero value, for example, a value of 1. For convenience, it will be assumed herein that the non-zero value is a value of 1.
For example, an (N, j, k) LDPC code is a linear block code having a block length N, and is defined by a sparse parity check matrix in which each column has j elements having a value of 1, each row has k elements having a value of 1, and all of the elements except for the elements having the value of 1 have a value of 0.
An LDPC code in which a weight of each column in the parity check matrix is fixed to ‘j’ and a weight of each row in the parity check matrix is fixed to ‘k’ as stated above, is called a “regular LDPC code.” The “weight” refers to the number of elements having a non-zero value among the elements constituting the generating matrix and parity check matrix. Unlike the regular LDPC code, an LDPC code in which the weight of each column in the parity check matrix and the weight of each row in the parity check matrix are not fixed is called an “irregular LDPC code.” It is generally known that the irregular LDPC code is superior in performance to the regular LDPC code. However, in the case of the irregular LDPC code, because the weight of each column and the weight of each row in the parity check matrix are not fixed, i.e. are irregular, the weight of each column in the parity check matrix and the weight of each row in the parity check matrix must be properly adjusted in order to guarantee the excellent performance.
With reference to FIG. 1, a description will now be made of a parity check matrix of an (8, 2, 4) LDPC code as an example of the (N, j, k) LDPC code.
FIG. 1 shows a parity check matrix of a general (8, 2, 4) LDPC code. A parity check matrix H of the (8, 2, 4) LDPC code is composed of 8 columns and 4 rows, wherein a weight of each column is fixed to 2 and a weight of each row is fixed to 4. Because the weight of each column and the weight of each row in the parity check matrix are regular, the (8, 2, 4) LDPC code shown in FIG. 1 is a regular LDPC code.
The parity check matrix of the (8, 2, 4) LDPC code has been described so far with reference to FIG. 1. Next, a factor graph of the (8, 2, 4) LDPC code described in connection with FIG. 1 will be described hereinbelow with reference to FIG. 2.
FIG. 2 shows a factor graph of the (8, 2, 4) LDPC code of FIG. 1. A factor graph of the (8, 2, 4) LDPC code is composed 8 variable nodes of x1 200, x2 202, x3 204, x4 206, x5 208, x6 210, x7 212 and x8 214, and 4 check nodes 216, 218, 220 and 222. When an element having a value of 1, i.e. a non-zero value, exists at the point where an ith row and a jth column of the parity check matrix of the (8, 2, 4) LDPC code cross each other, a branch is created between a variable node xi and a jth check node.
Because the parity check matrix of the LDPC code has a very small weight as described above, it is possible to perform decoding through iterative decoding even in a block code having a relatively long size, that exhibits performance approximating a channel capacity limit of Shannon's channel coding theorem, such as a turbo code, while continuously increasing a block size of the block code. MacKay and Neal have proven that an iterative decoding process of an LDPC code using a flow transfer scheme approximates an iterative decoding process of a turbo code in performance.
In order to generate a high-performance LDPC code, the following conditions should be satisfied.
(1) Cycles in a factor graph of an LDPC code should be considered.
The term “cycle” refers to a loop formed by the edges connecting the variable nodes to the check nodes in a factor graph of an LDPC code, and a length of the cycle is defined as the number of edges constituting the loop. A long cycle means that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is large. In contrast, a short cycle means that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is small.
As cycles in the factor graph of the LDPC code become longer, the performance efficiency of the LDPC code increases, for the following reasons. That is, when long cycles are generated in the factor graph of the LDPC code, it is possible to prevent performance degradation, such as an error floor, occurring when too many cycles with a short length exist in the factor graph of the LDPC code.
(2) Efficient coding of an LDPC code should be considered.
It is difficult for the LDPC code to undergo real-time coding compared with a convolutional code or a turbo code because of its high coding complexity. In order to reduce the coding complexity of the LDPC code, a Repeat Accumulate (RA) code has been proposed. However, the RA code also has a limitation in reducing the coding complexity of the LDPC code. Therefore, efficient coding of the LDPC code should be taken into consideration.
(3) Degree distribution in a factor graph of an LDPC code should be considered.
Generally, an irregular LDPC code is superior in performance to a regular LDPC code, because a factor graph of the irregular LDPC code has various degrees. The term “degree” refers to the number of edges connected to the variable nodes and the check nodes in the factor graph of the LDPC code. Further, the phrase “degree distribution in a factor graph of an LDPC code” refers to a ratio of the number of nodes having a particular degree to the total number of nodes. It has been proven by Richardson that an LDPC code having a particular degree distribution is superior in performance.
Meanwhile, with the development of communication systems, various schemes such as a Hybrid Automatic Retransmission reQuest (HARQ) scheme and an Adaptive Modulation and Coding (AMC) scheme are used to increase resource efficiency while supporting high-capacity data transmission.
The HARQ scheme is classified into a Type-1 scheme and a Type-2 scheme. The Type-1 scheme is generally called a Chase Combining technique, and in the Type-1 scheme, information bits are encoded by a channel code having an appropriate coding rate before being transmitted. That is, if a receiver, after performing decoding, detects an error by a Cyclic Redundancy Code (CRC), it sends a retransmission request to a transmitter. Then the transmitter retransmits the same block as the transmitted block, and the receiver calculates a new received value by adding the newly received block to the previously received block in units of symbols or bits. Thereafter, the receiver performs decoding on the channel code using the calculated value.
It is known that among the currently proposed schemes, the Type-2 scheme shows the best performance. The Type-2 scheme can be used only for the channel code implemented such that it is rate-compatible. In a retransmission process, the Type-2 scheme transmits only the new parity bits rather than transmitting the same block as the previously transmitted block.
FIG. 3 shows a general Type-2 HARQ scheme. A hatched block shown by reference numeral 310 represents information bits, and hatched blocks shown by reference numeral 330 represent parity bits. A receiver generates a low-coding rate channel code by adding parity bits to the previously received data. In a retransmission process, the receiver performs decoding using a channel code having a lower coding rate than that used in the previous transmission process. In the Type-2 scheme, the performance is greatly affected by the method of designing a high-performance rate-compatible channel code.
In order to use the HARQ scheme and the AMC scheme, there is a need to support various coding rates. However, because the LDPC code has a limitation in terms of the coding rate as described above, it is difficult to support various coding rates. In addition, in order to use the HARQ scheme, it is necessary to create a code having various coding rates using one encoder. Therefore, there is a need for a method capable of creating LDPC codes having various coding rates using one encoder.